1. Field of the Invention
In a multiprocessor environment with threads and preemptive scheduling, threads generally participate in a mutual exclusion protocol for synchronization purposes, for example to ensure that only one thread has access to a shared resource (e.g., critical sections of memory) at a given time. Mutual exclusion protocols employ lock constructs (also referred to as “mutex” constructs) in which a lock is either in unlocked state or in a locked state, in which case a single thread is said to “own” the lock. The lock owner is permitted to access the shared resource protected by the lock. If another thread attempts to obtain ownership of a lock while the lock is owned, the other thread will not be permitted to access the shared resource until the lock owner releases the lock and the other thread successfully acquires ownership of the lock.
2. Background Art
Typically, a lock object contains an owner field that identifies the thread that owns the lock. When the owner field is NULL the lock is unowned. In some implementations, the lock object may also include a queue that identifies “blocked” threads, which are threads whose execution has been suspended while they are waiting to acquire the lock. Commonly, a thread attempts to gain ownership of a lock by using a test-and-set type of instruction (such as CAS (compare-and-swap) in SPARC®, CMPXCHG on Intel's IA32 processor) which atomically replaces a NULL value in the owner field with an identifier of the acquiring thread. The replacement only occurs if the owner field is found to be NULL during the compare part of the instruction. If the instruction succeeds, the acquiring thread is then said to own or hold the lock. If the instruction fails, i.e., the owner field is found to be non-NULL then the acquiring thread is not permitted to access the shared resource. In this case the acquiring thread generally takes one of three actions: (1) spin, (2) block, or (3) sleep/yield. Each of is discussed in turn below.
When an acquiring thread spins, it executes a loop of instructions in which the owner field of the lock is periodically polled, waiting for the thread owner to release the lock. If the spinning thread observes a NULL value in the owner field, the thread executes a test-and-set instruction to try to gain ownership of the lock. If the instruction succeeds, the thread becomes the owner and is permitted to access the shared resource. If the instruction fails, the thread continues spinning. Generally, the thread can perform no useful work when it is spinning, and therefore makes no progress in its computational tasks. Spinning is sometimes referred to as “busy waiting”.
When an acquiring thread blocks, its execution is suspended indefinitely by the operating system 32—it becomes ineligible for dispatch onto a processor by a scheduler within the operating system 32. The scheduler selects and dispatches another thread. The thread that is currently the lock owner will normally be dispatched at some point, in which case it will release the lock as part of its execution. When the lock owner eventually releases the lock, it “wakes” the thread from its blocked status. This causes the status of the blocked thread to change to “runnable”, meaning it becomes eligible for dispatch onto a processor, whereupon it can again compete for ownership of the lock.
When a thread blocks, the processor becomes idle if no ready threads are available. Additionally, blocking generally results in a context switch, which consumes processing cycles and can interfere with efficient operation of a processor's memory address translation and data caching mechanisms.
There are hybrid “spin-block” or spin-then-block implementations that spin for some period and then revert to blocking. The synchronization subsystems in various Java® Virtual Machine (VM) implementations use a spin-block strategy. Sleeping and yielding are both implemented with calls to the operating system's scheduler. The acquiring thread can sleep, which temporarily blocks the thread for some short interval. During this interval, other threads may run on the processor. Yielding requests that the scheduler check its ready queues, and if any other threads are ready the scheduler suspends execution of the yielding thread and immediately dispatches one of the ready threads. If no ready threads exist, the yield operation returns immediately and the acquiring thread continues executing. Both sleeping and yielding generally result in a context switch.